#pragma once
#include <assert.h>

namespace qian
{
	template<class T>
	// 当一个类不想要访问限定符限制的时候就用struct
	// 注意：如果这里写成了class 就是模板了 模板是不会被编译的只有在实例化的时候才会
	struct ListNode
	{
		ListNode<T>* _next;
		ListNode<T>* _prev;

		T _data;
		//书写其构造函数，则下面的 _head = new Node() 里面要加参数
		ListNode(const T& data = T())//写成全缺省，避免下面的不带参问题
			:_next(nullptr)
			,_prev(nullptr)
			,_data(data)
		{}
	};

	///*由于Node*不符合遍历的行为，因为Node*为自定义类型，必须要有内置类型，才能通过编译
	//Listlterator类封装Node*
	//再通过重载运算符控制其行为*/
	template<class T, class Ref, class Ptr>
	struct ListIterator
	{
		typedef ListNode<T> Node;
		typedef ListIterator<T, Ref, Ptr> Self;

		Node* _node;
		ListIterator(Node* node)
			:_node(node)
		{}

		Self& operator++()
		{
			_node = _node->_next;
			return *this;
		}
		Self& operator--()
		{
			_node = _node->_prev;
			return *this;
		}
		Self operator++(int)
		{
			Self tmp(*this);
			_node = _node->_next;
			return tmp;
		}
		Self operator--(int)
		{
			Self tmp(*this);
			_node = _node->_prev;
			return tmp;
		}

		Ptr operator->()
		{
			return &_node->_data;
		}
		Ref operator*()
		{
			return _node->_data;
		}
		bool operator!=(const Self& it)
		{
			return _node != it._node;
		}

		bool operator==(const Self& it)
		{
			return _node == it._node;
		}
	};

	//反向迭代器
	template<class iterator, class Ref, class Ptr>
	struct Reverse_ListIterator
	{
		typedef Reverse_ListIterator<iterator, Ref, Ptr> Self;

		iterator _it;

		Reverse_ListIterator(iterator it)
			:_it(it)
		{}

		Self& operator++()
		{
			_it._node = _it._node->_prev;
			return *this;
		}
		Self& operator--()
		{
			_it._node = _it._node->_next;
			return *this;
		}
		Self operator++(int)
		{
			Self tmp(*this);
			_it._node = _it._node->_prev;
			return tmp;
		}
		Self operator--(int)
		{
			Self tmp(*this);
			_it._node = _it._node->_next;
			return tmp;
		}

		Ptr operator->()
		{
			return &_it._node->_prev->_data;
		}

		Ref operator*()
		{
			iterator tmp = _it;
			return tmp._node->_prev;
		}
		bool operator!=(const Self& it)
		{
			return _it._node != it._it._node;
		}

		bool operator==(const Self& it)
		{
			return _it._node == it._node;
		}
	};

	template<class T>
	class list
	{
		typedef ListNode<T> Node;
	public:	
			//通过模板，给不同模板参数，让编译器帮我们写两个类（实例化）
			typedef ListIterator<T, T&, T*> iterator;
			typedef ListIterator<T, const T&, const T*> const_iterator;

			//反向迭代器
			typedef Reverse_ListIterator<iterator, T&, T*> reverse_iterator;
			typedef Reverse_ListIterator<iterator,const T&, const T*> const_reverse_iterator;

			iterator begin()
			{
				return iterator(_head->_next);
			}
			iterator end()
			{
				return iterator(_head);
			}
			const_iterator begin() const 
			{
				return const_iterator(_head->_next);
			}
			const_iterator end() const
			{
				return const_iterator(_head);
			}

			//反向迭代器
			reverse_iterator rbegin()
			{
				return reverse_iterator(end());
			}
			reverse_iterator rend()
			{
				return reverse_iterator(begin());
			}
			const_reverse_iterator rbegin() const
			{
				return const_reverse_iterator(end());
			}
			const_reverse_iterator rend() const
			{
				return const_reverse_iterator(begin());
			}

			void empty_init()
			{
				_head = new Node(T());
				_head->_next = _head;
				_head->_prev = _head;
			}

			list()
			{
				empty_init();
			}

			list(initializer_list <T> il)
			{
				empty_init();
				for (const auto& e : il)
				{
					push_back(e);
				}
			}

			//l2 (l1)
			list(const list<T>& lt)
			{
				empty_init();
				for (const auto& e : lt)
				{
					push_back(e);
				}
			}

			//l1 = l2;
			list<T>& operator = (list<T>lt)
			{
				swap(_head, lt._head);
				return *this;
			}

			~list()
			{
				clear();
				delete _head;
			}

			void push_back(const T& x)
			{
				/*Node* newnode = new Node(x);
				Node* tail = _head->_prev;

				tail->_next = newnode;
				newnode->_prev = tail;
				newnode->_next = _head;
				_head->_prev = newnode;*/
				
				insert(end(), x);
			}

			void pop_back()
			{
				erase(--end()); //记得减减
			}

			void push_front(const T &x)
			{
				insert(begin(), x);
			}
			void pop_front()
			{
				erase(begin());
			}
			
			iterator insert(iterator pos, const T& x)
			{
				Node* node = new Node(x);
				Node* cur = pos._node;
				Node* prev = cur->_prev;

				node->_next = cur;
				node->_prev = prev;
				prev->_next = node;
				cur->_prev = node;

				return iterator(node);
			}

			iterator erase(iterator pos)
			{
				assert(pos != end());
				Node* cur = pos._node;
				Node* prev = cur->_prev;
				Node* next = cur->_next;

				prev->_next = next;
				next->_prev = prev;
				delete cur;
				return iterator(next);
			}

			void clear() //清除所有数据
			{
				list<T>::iterator it = begin();
				while (it != end())
				{
					it = erase(it);
				}
			}
	private:
		Node* _head;
	};

	void Func(const list<int>& lt) //const 迭代器
	{
		//const iterator const  迭代器不能是普通迭代器前面加const修饰
		//const 迭代器目标本身可以修改，指向内容不可以修改，类似于const T* p
		//const list<int>::iterator it = lt.begin(); //那么it无法++，因为const改变

		list<int>::const_iterator it = lt.begin();
		while (it != lt.end())
		{
			//指向的内容不能修改
			//*it += 10;

			cout << *it << " ";
			++it;
		}
		cout << endl;
	}

	void test1()
	{
		//用于检查最上面的struct和class，细节不会被编译，模板才会
		//按需实例化（不调用就不实例化这个成员函数）
		list<int> l1;
		l1.push_back(1);
		l1.push_back(2);
		l1.push_back(3);
		l1.push_back(4);
		l1.push_back(5);

		Func(l1);

		//迭代器遍历
		// ListIterator<int> it = l1.begin();
		list<int>::iterator it = l1.begin();
		while (it != l1.end())
		{
			*it += 10;
			cout << *it << " ";
			++it;
		}
		cout << endl;

		for (auto e : l1)
		{
			cout << e << " ";
		}
		cout << endl;
	}
	
	struct Pos
	{
		int _row;
		int _col;
		Pos(int row = 0,int col =0)
			:_row(row)
			,_col(col)
		{}
	};

	void test2()
	{
		cout << "正向迭代器：" << endl;

		list<Pos>l1;
		l1.push_back(Pos(100,100));
		l1.push_back(Pos(200,200));
		l1.push_back(Pos(300,300));
		list<Pos>::iterator it = l1.begin();
		while (it != l1.end())
		{
			cout << it->_row << ":" << it->_col << endl;
			cout << it.operator->()->_row << ":" << it.operator->()->_col << endl;
			++it;
		}
		cout << endl;

		cout << "反向迭代器：" << endl;
		qian::list<Pos>::reverse_iterator it1 = l1.rbegin();
		while (it1 != l1.rend())
		{
			//cout << (*it)._row << ":" << (*it)._col << endl;
			// 为了可读性，省略了一个->
			cout << it1->_row << ":" << it1->_col << endl;
			//cout << it->->_row << ":" << it->->_col << endl;
			cout << it1.operator->()->_row << ":" << it1.operator->()->_col << endl;

			++it1;
		}
		cout << endl;
	}

	void test3()
	{
		list<int> l1;
		l1.push_back(1);
		l1.push_back(2);
		l1.push_back(3);
		l1.push_back(4);
		l1.push_back(5);

		Func(l1);

		l1.push_front(10);
		l1.push_front(20);
		l1.push_front(30);

		Func(l1);

		l1.pop_front();
		l1.pop_front();
		Func(l1);

		l1.pop_back();
		l1.pop_back();
		Func(l1);

		//避免删除哨兵点
		/*l1.pop_back();
		l1.pop_back();
		l1.pop_back();
		l1.pop_back();
		l1.pop_back();
		Func(l1);*/
	}

	void test4()
	{
		list<int> l1,l2;
		for (int i = 1; i <= 4; i++) l1.push_back(i);
		l2 = l1; //赋值

		for (const auto& e : l2) cout << e << " ";
		cout << endl;

		l1.push_back(5);
		list<int> l3(l1); // 拷贝
		for (const auto& e : l3) cout << e << " ";
		cout << endl;
	}

	void test5()
	{
		list<int> l1 = { 1,2,3,4,5,6 };
		Func(l1);
		cout << typeid(string::iterator).name() << endl;
		cout << sizeof(string::iterator) << endl;
	}
}